package com.cskaoyan.javase.recursion._2hanoi;

/**
 * 汉诺塔（Hanoi）问题，是经典的递归问题,学习递归一般都绕不开它，这里我们就学习一下如何使用递归求解汉诺塔问题。
 *
 * 首先看一下汉诺塔问题的描述：
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 * 假设对于N个盘子的汉诺塔问题,至少需要f(N)步来完成
 *
 * 分析:
 *      要想把塔1上所有的盘子,从塔1 --> 塔3
 *      必须保证塔3是空的,并且塔1上除了最大盘子外的所有盘子(N-1个)全部在塔2上,这时才能将塔1上的最大盘子移到塔3
 *      然后再将塔2上的所有盘子从塔2移到塔3即可
 *
 * 开始分解的思想:
 *      1.无论N等于多少,必不可少的一步是,将塔1上最大的盘子移到塔3,这需要1步.
 *      2.为了保证上述步骤能够正常进行,需要保证除最大盘子外的所有盘子(N-1个)都在塔2上
 *          也就是说,这一步,需要将(N-1)个盘子,从塔1移到塔2上去
 *          这其实(N-1)个盘子的汉诺塔问题
 *      3.将第1步进行完毕后,现在最大的盘子在塔3上,(N-1)个盘子在塔2上
 *          于是再将(N-1)个盘子从塔2移到塔3,就能够完成汉诺塔问题了
 *          这其实仍然是(N-1)个盘子的汉诺塔问题
 *     综上所述:
 *          f(N) = f(N-1) + 1 + f(N-1) 这就是分解得到的递归体
 *          并且上述分解不可能一直分解下去
 *              因为f(2) = 3
 *              f(1) = 1 递归的出口
 *
 * 求f(N)的通项公式:
 *      f(N) = f(N-1) + 1 + f(N-1)
 *      f(N) = 2f(N-1) + 1
 *      f(N) + 1 = 2f(N-1) + 2
 *      f(N) + 1 = 2(f(N-1) + 1)
 *      (f(N) + 1)/ (f(N-1) + 1) = 2 是典型的等比数列
 *      f(N) + 1 = 2^n
 *      f(N) = 2^n - 1
 *
 *
 * @since 16:06
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(10));
    }

    public static long hanoi(int n) {
        if (n == 2) {
            return 3;
        }
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
